// Z函数
// https://soj.turingedu.cn/problem/60503/
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
using ll = long long;
using T = int;
T rad(); // quick read
const int inf = 0x3f3f3f3f;
#define rf(i, n) for (int i = 1; i <= (n); ++i)
#define rep(i, s, t, d) for (int i = (s); i <= (t); i += (d))
const int max_size = 5 + 100;
const int maxn = 5 + 2e5;

char s[maxn];
int z[maxn];

void Zcal(const char *s, int len, int *z) {
    z[0] = 0;
    for (int i = 1, l = 0, r = -1; i < len; ++i) {
        int tmp = i > r ? 0 : min(z[i - l], r - i + 1);
        while (i + tmp < len && s[tmp] == s[i + tmp])
            ++tmp;
        z[i] = tmp--;
        if (i + tmp > r) l = i, r = i + tmp;
    }
}

int cnt[maxn]; // cnt[i] 是 z(x) 大于 i 的数量，

int main() {
    int q = rad();
    rf(p, q) {
        memset(cnt, 0, sizeof(cnt));
        scanf("%s", s);
        int len = strlen(s);
        Zcal(s, len, z), z[0] = len;  // 调整 z[0]
        for (int i = 0; i < len; ++i) // 数组计数
            cnt[z[i]]++;
        for (int i = len - 1; i >= 0; --i) // 后缀和
            cnt[i] += cnt[i + 1];
        printf("Case #%d:\n", p);
        for (int i = len - 1; i >= 0; --i) {        // 保证完全匹配区间长度递减
            if (i + z[i] == len)                    // 完全匹配
                printf("%d %d\n", z[i], cnt[z[i]]); // z值更大的节点也完全匹配（本质上在枚举左端点）
        }
    }
}

T rad() {
    T back = 0;
    int ch = 0, posi = 0;
    for (; ch < '0' || ch > '9'; ch = getchar())
        posi = ch ^ '-';
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        back = (back << 1) + (back << 3) + (ch & 0xf);
    return posi ? back : -back;
}
